package dp.备忘录dfs;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 猜数字大小373.java
 * @createTime 2024年03月27日 09:51:00
 */
public class 猜数字大小ii375 {
	/*

	 */
	int[][] memo;

	public int getMoneyAmount(int n) {
		memo = new int[n + 1][n + 1];
		return dfs(1, n);
	}

	public int dfs(int left, int right) {
		if (left >= right) {
			return 0;
		}
		if (memo[left][right] != 0) {
			return memo[left][right];
		}
		int ans = Integer.MAX_VALUE;
		for (int i = left; i <= right; i++) {
			//选择i的时候，至少需要cur 才能猜中
			int cur = Math.max(dfs(left, i - 1), dfs(i + 1, right)) + i;
			ans = Math.min(cur, ans);
		}
		memo[left][right] = ans;
		return ans;
	}
}
